package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Random;

public class ShuffleAnArray {

	private final int[] nums;
//	private List<Integer> list = new ArrayList<Integer>();
	private Random random;

	private int[] res;
	
	public ShuffleAnArray(int[] nums) {
		this.nums = nums;
//		for (int i = 0; i < nums.length; i++) {
//			list.add(nums[i]);
//		}
		res = new int[nums.length];
		random = new Random();
	}

	/** Resets the array to its original configuration and return it. */
	public int[] reset() {
//		list.clear();
//		for (int i = 0; i < nums.length; i++) {
//			list.add(nums[i]);
//		}
		return nums;
	}

	/** Returns a random shuffling of the array. */
	public int[] shuffle() {
//		Collections.shuffle(list);
//		int size = list.size();
//		for (int i = 0; i < size; i++) {
//			res[i] = list.get(i);
//		}
//		return res;
		
		//other's code with prove
//		For the 0th element, the probability for that it stays at index 0 position, 
//		is 1/1 * (2-1)/2 * (3-1)/3 * ... (n-1)/n = 1/n. 
//		The probability for that it will stay at index 1 is 1/2 * (3-1)/3 * ... = 1/n. 
//		This means for the 0th element, it has 1/n probability to be placed into any position.
//
//		Once we know that 0th element will stay at index x, for simplicity, we know that 0th element 
//		will stay at index 0, then what is the probability of 1st element to stay 1st position? 
//		it is 1/1 * 1/2 * ... (n-2)/(n-1) = 1/(n-1). This implies that for the 1st element, 
//		it has 1/(n-1) probability to be placed into any un-occupied position.
//
//		Not quite sure whether we can do the above analysis by fixing 0th element's position.
//
//		Then one complete sequence will have probability of 1/(n!) to be chosen, which fits the requirement.
		if(nums == null) return null;
        int[] a = nums.clone();
        for(int j = 1; j < a.length; j++) {
            int i = random.nextInt(j + 1);
            swap(a, i, j);
        }
        return a;
	}
	
	public void swap(int[] array, int i, int j){
		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}
}
